package com.bolins.math.merge;

import java.util.Arrays;

import com.bolins.math.Sortor;

/**
 * 合并排序算法,实现排序接口(升序)
 * 
 * 分治方法
 * 
 * @author liuys
 * 
 */
public class MergeSortor implements Sortor {

	@Override
	public int[] exeSort(int[] input) {
		mergeSort(input, 0, input.length - 1);
		return input;
	}

	/**
	 * 每次分治包括三个操作：将要排序的数组分成两个子数组并分别排序，再将两个子数组排序并合并成一个数组
	 * 伪代码:
	 * 		if l<h
	 * 			then m <-- (l+h)/2
	 * 			     mergeSort(input,l,m);
	 * 				 mergeSort(input,m+1,h);
	 * 				 merge(input,l,m,h);
	 * @param input
	 * @param l
	 * @param h
	 */
	private void mergeSort(int[] input, int l, int h) {
		if (l < h) {
			int m = (l + h) / 2;
			mergeSort(input, l, m);
			mergeSort(input, m + 1, h);
			merge(input, l, m, h);
		}
	}

	/**
	 * 思路:  
	 * 		 从两个要合并的数组中各取一个数进行比较，将较小的一个放到输出数组中，
	 * 		 并从较小数所在数组中再取出一个进行比较，直到某个数组中的数取完，
	 * 		 则将另一个数组中剩下的数直接放到输出数组后面
	 * 
	 * 伪代码：
	 * 		tempA <-- input[l....m];
	 * 		tempB <-- input[m+1...h];
	 * 		i <-- l,a <-- 0,b <-- 0;
	 * 		while i<=h 
	 * 			do if a < length(tempA) and b < length(tempB)
	 * 			   		then if tempA[a] < tempB[b]
	 * 						 		then input[i] <-- tempA[a];
	 * 									 a <-- a+1;
	 * 						 		else input[i] <-- tempB[b];
	 * 									 b <-- b+1;
	 * 			   		else if a == length(tempA)
	 * 							then input[i] <-- tempB[b];
	 * 							 	 b <-- b+1;
	 * 			   		else if b == length(tempB)
	 * 							then input[i] <-- tempA[a];
	 * 							 	 a <-- a+1;
	 * 			   i <-- i+1; 
	 * @param input
	 * @param l
	 * @param m
	 * @param h
	 */
	private void merge(int[] input, int l, int m, int h) {
		int[] tempA = Arrays.copyOfRange(input, l, m + 1);
		int[] tempB = Arrays.copyOfRange(input, m + 1, h + 1);
		int i = l, a = 0, b = 0;
		while (i <= h) {
			if ((a < tempA.length && b < tempB.length && tempA[a] < tempB[b])
					|| (b == tempB.length)) {
				input[i] = tempA[a];
				a++;
			} else if ((a < tempA.length && b < tempB.length && tempA[a] >= tempB[b])
					|| (a == tempA.length)) {
				input[i] = tempB[b];
				b++;
			}
			i++;
		}
	}

}
